# 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：[[3],[9,20],[15,7]]
#
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def levelOrder(self, root):
        stack = []
        res = []
        if not root:
            return res
        stack.append(root)
        while stack:
            size = len(stack)
            tmp = []
            while size:
                node = stack.pop(0)
                tmp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
                size -= 1
            res.append(tmp)
        return res

    def levelOrder2(self, root): # 递归法,迷迷糊糊的
        res = []
        def helper(root,depth):
            if not root:
                return []
            if len(res) == depth:
                res.append([])
            res[depth].append(root.val)
            if root.left:helper(root.left,depth+1)
            if root.right:helper(root.right,depth+1)
        helper(root,0)
        return res



if __name__ == '__main__':
    root = [3, 9, 20, None, None, 15, 7]
    a32 = TreeNode(7)
    a31 = TreeNode(15)
    a21 = TreeNode(9)
    a22 = TreeNode(20,a31,a32)
    a11 = TreeNode(3,a21,a22)
    # 需要自己构建树
    tmp = Solution()
    res = tmp.levelOrder(a11)
    print(res)
